#include <stdio.h>
#include <stdlib.h>

//最大顶点个数
#define MAX_VERTEX_NUM 20
//顶点数据的类型
#define VertexType int
//图中弧或者边包含的信息的类型
#define InfoType int

typedef struct ArcNode
{
    /* data */
    //邻接点在数组中的位置下标
    int adjVex;
    //指向下一个邻接点的指针
    struct ArcNode * next;
    InfoType * info;
}ArchNode;

//存储各链表头结点的数组
typedef struct VNode
{
    //顶点的数据域
    VertexType data;
    //指向邻接点的指针
    ArchNode * firstArc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
    //图中顶点的数组
    AdjList vertices;
    //记录图中顶点数和边或弧数
    int verxnum, arcnum;
    //记录图的种类
    int kind;
}ALGraph;

//构造有向图
void CreateDG(ALGraph *G) {
    //输入图含有的顶点数和弧的个数
    G->verxnum = 4;
    G->arcnum = 4;
    //依次输入顶点本身的数据
    for(int i = 0 ; i < G->verxnum; i++) {
        G->vertices[i].data = i;
        G->vertices[i].firstArc = NULL;
    }
    ArchNode *p;
    //邻接表存储有向图
    /*
    0:v1->2->1
    1:v2
    2:v3->3
    3:v4->0
    */
    //在顶点链表中添加邻接点的数据
    /*
    0:v1->2->1
    */
    p = (ArchNode *)malloc(sizeof(ArchNode));
    /* 邻接序号 */
    p->adjVex = 2;
    /* 将p的指针指向当前顶点上指向的结点 */
    p->next = G->vertices[0].firstArc;
    /* 将当前顶点的指针指向p */
    G->vertices[0].firstArc = p;
    //保存firstArc地址
    ArchNode * tempFirstArc = G->vertices[0].firstArc;
    p = (ArchNode *)malloc(sizeof(ArchNode));
    /* 邻接序号 */
    p->adjVex = 1;
    /* 将p的指针指向当前顶点上指向的结点 */
    p->next = G->vertices[1].firstArc;
    /* 将最后一个节点的指针指向tempFirstArc */
    G->vertices[0].firstArc->next = p;

    /*
    2:v3->3
    */
    p = (ArchNode *)malloc(sizeof(ArchNode));
    /* 邻接序号 */
    p->adjVex = 3;
    /* 将p的指针指向当前顶点上指向的结点 */
    p->next = G->vertices[2].firstArc;
    /* 将当前顶点的指针指向p */
    G->vertices[2].firstArc = p;

    /*
    3:v4->0
    */
   p = (ArchNode *)malloc(sizeof(ArchNode));
    /* 邻接序号 */
    p->adjVex = 0;
    /* 将p的指针指向当前顶点上指向的结点 */
    p->next = G->vertices[3].firstArc;
    /* 将当前顶点的指针指向p */
    G->vertices[3].firstArc = p;
}

void PrintGraph(ALGraph G) {
    for(int i = 0 ; i < G.verxnum; i++) {
        printf("%d: ", G.vertices[i].data);
        ArchNode * temp = G.vertices[i].firstArc;
        while(temp != NULL) {
            printf("%d ", temp->adjVex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    ALGraph G;
    CreateDG(&G);
    PrintGraph(G);
    return 0;
}